#ifndef ArvBin_
#define ArvBin_

#include <queue>
#include "ArvBinNodo.h"

template<class T>
class ArvBin {
protected:
	ArvBinNodo<T>* raiz;

	ArvBinNodo<T>* copiar(ArvBinNodo<T>* rz);
	void destroiArv(ArvBinNodo<T>* rz);

	ArvBinNodo<T>* pesquisa(const T& x, ArvBinNodo<T>* rz) const;
	ArvBinNodo<T>* pesquisaAnt(const T& x, ArvBinNodo<T>* rz) const;

	void preOrdem(ArvBinNodo<T>* rz) const;
	void posOrdem(ArvBinNodo<T>* rz) const;
	void emOrdem(ArvBinNodo<T>* rz) const;
	void listarPorNivel(ArvBinNodo<T>* rz) const;

	int altura(ArvBinNodo<T>* rz) const;

	void Valores_Em_Ordem(ArvBinNodo<T>* rz, std::queue<T> & valores) const;

public:
	ArvBin();
	ArvBin(const ArvBin<T> & arv);
	~ArvBin();

	void fazerArv(const T & elem, ArvBin<T> & a1, ArvBin<T> & a2);

	bool vazia() const;

	void preOrdem() const;
	void posOrdem() const;
	void emOrdem() const;
	void listarPorNivel() const;

	void altura() const;

	bool pesquisa(T &x) const;

	void eliminar(const T &x);

	void Nos_Por_Nivel() const;

	ArvBin<T> & operator=(const ArvBin<T> & o);

	bool E_BST_Valida();

};

//Construtor por defeito
template<class T>
ArvBin<T>::ArvBin() {
	raiz = NULL;
}

template<class T>
ArvBinNodo<T>* ArvBin<T>::copiar(ArvBinNodo<T>* rz) {
	if (rz == NULL)
		return NULL;

	ArvBinNodo<T>* n = new ArvBinNodo<T>;

	n->setInf(rz->getInf());
	n->setEsq(copiar(rz->getEsq()));
	n->setDir(copiar(rz->getDir()));

	return n;
}

// Construtor copia
template<class T>
ArvBin<T>::ArvBin(const ArvBin<T> & arv) {
	raiz = copiar(arv.raiz);
}

template<class T>
void ArvBin<T>::destroiArv(ArvBinNodo<T>* rz) {
	if (rz != NULL) {
		destroiArv(rz->getEsq());
		destroiArv(rz->getDir());
		delete rz;
	}
}

template<class T>
ArvBin<T>::~ArvBin() {
	destroiArv(raiz);
	raiz = NULL;
}

template<class T>
bool ArvBin<T>::vazia() const {
	return (raiz == NULL);
}

template<class T>
void ArvBin<T>::preOrdem() const {
	std::cout << "\nVISITA PRE-ORDEM\n";
	preOrdem(this->raiz);

	std::cout << std::endl;
}

template<class T>
void ArvBin<T>::preOrdem(ArvBinNodo<T>* rz) const {
	if (rz != NULL) {
		std::cout << rz->getInf() << " ";
		preOrdem(rz->getEsq());
		preOrdem(rz->getDir());
	}
}

template<class T>
void ArvBin<T>::posOrdem() const {
	std::cout << "\nVISITA POS-ORDEM\n";
	posOrdem(this->raiz);

	std::cout << std::endl;
}

template<class T>
void ArvBin<T>::posOrdem(ArvBinNodo<T>* rz) const {
	if (rz != NULL) {
		posOrdem(rz->getEsq());
		posOrdem(rz->getDir());
		std::cout << rz->getInf() << " ";
	}
}

template<class T>
void ArvBin<T>::emOrdem() const {
	std::cout << "\nVISITA EM ORDEM (OU SIMETRICA)\n";
	emOrdem(this->raiz);

	std::cout << std::endl;
}

template<class T>
void ArvBin<T>::emOrdem(ArvBinNodo<T>* rz) const {
	if (rz != NULL) {
		emOrdem(rz->getEsq());
		std::cout << *(rz->getInf()) << " ";
		emOrdem(rz->getDir());
	}
	return;
}

template<class T>
void ArvBin<T>::listarPorNivel() const {
	std::cout << "\nVISITA POR NIVEIS\n";
	listarPorNivel(raiz);

	std::cout << std::endl;
}

template<class T>
void ArvBin<T>::listarPorNivel(ArvBinNodo<T>* rz) const {
	std::queue<ArvBinNodo<T>*> q;
	ArvBinNodo<T>* p;

	if (rz != NULL)
		q.push(rz);

	while (!q.empty()) {
		p = q.front();
		q.pop();
		std::cout << p->getInf() << " ";
		if (p->getEsq() != NULL)
			q.push(p->getEsq());
		if (p->getDir() != NULL)
			q.push(p->getDir());
	}
}

template<class T>
void ArvBin<T>::altura() const {
	std::cout << "\nALTURA DA ARVORE: " << altura(raiz) << std::endl;
}

template<class T>
int ArvBin<T>::altura(ArvBinNodo<T>* rz) const {
	int nesq, ndir;

	if (rz == NULL)
		return -1;
	else {
		nesq = altura(rz->getEsq());
		ndir = altura(rz->getDir());

		return (nesq > ndir ? nesq + 1 : ndir + 1);
	}
}

// Constroi uma Arv Bin das folhas para a raiz 
template<class T>
void ArvBin<T>::fazerArv(const T& elem, ArvBin<T>& a1, ArvBin<T>& a2) {
	raiz = new ArvBinNodo<T>(elem, a1.raiz, a2.raiz);
	a1.raiz = NULL;
	a2.raiz = NULL;
}

template<class T>
ArvBinNodo<T>* ArvBin<T>::pesquisa(const T & x, ArvBinNodo<T>* rz) const {
	ArvBinNodo<T>* n;

	if (rz != NULL) {
		if (rz->getInf() == x)
			return rz;

		n = pesquisa(x, rz->getEsq());

		if (n == NULL)
			n = pesquisa(x, rz->getDir());

		return n;
	} else
		return NULL;
}

template<class T>
bool ArvBin<T>::pesquisa(T& x) const {
	ArvBinNodo<T>* ap = pesquisa(x, raiz);

	if (ap != NULL) {
		if (ap->getInf() == x)
			x = ap->getInf();

		return true;
	} else
		return false;
}

template<class T>
ArvBinNodo<T>* ArvBin<T>::pesquisaAnt(const T & x, ArvBinNodo<T>* rz) const {
	ArvBinNodo<T>* n;

	if (rz == NULL)
		return rz;

	if (rz->getEsq() != NULL)
		if (rz->getEsq()->getInf() == x)
			return rz;

	if (rz->getDir() != NULL)
		if (rz->getDir()->getInf() == x)
			return rz;

	n = pesquisaAnt(x, rz->getEsq());

	if (n == NULL)
		n = pesquisaAnt(x, rz->getDir());

	return n;
}

// Elimina a subarvore cuja raiz=x. 

template<class T>
void ArvBin<T>::eliminar(const T & x) {
	ArvBinNodo<T>* ant;

	ant = pesquisaAnt(x, raiz);

	if (ant == NULL) {
		if (raiz->getInf() == x) //elimina toda a arvore
				{
			destroiArv(raiz);
			raiz = NULL;
		} else
			std::cout << "Elemento a eliminar nao existe " << std::endl;
	} else { //elimina subarvore
		if (ant->getEsq()) {
			if (ant->getEsq()->getInf() == x) {
				destroiArv(ant->getEsq());
				ant->setEsq(NULL);
			} else if (ant->getDir()) {
				if (ant->getDir()->getInf() == x) {
					destroiArv(ant->getDir());
					ant->setDir(NULL);
				}
			}
		}
	}
}

/*
 *
 * ComeÃ§a aqui a resoluÃ§Ã£o dos exercÃ­cios das aulas PL.
 *
 */

template<class T>
void ArvBin<T>::Nos_Por_Nivel() const {
	int nos_nivel_actual, nos_proximo_nivel, nivel;
	std::queue<ArvBinNodo<T> *> nos_a_processar;

	std::cout << "\nNUMERO DE NOS POR NIVEL:\n";
	if (raiz == NULL) {
		std::cout << "Arvore vazia!\n";
		return;
	}

	nos_nivel_actual = 0;
	nos_proximo_nivel = 1;
	nivel = 0;

	nos_a_processar.push(raiz);

	while (!nos_a_processar.empty()) {
		nos_nivel_actual = nos_proximo_nivel;
		nos_proximo_nivel = 0;
		nivel++;

		std::cout << "Nivel " << nivel << ": " << nos_nivel_actual << " no(s)\n";

		for (int i = 0; i < nos_nivel_actual; i++) {
			ArvBinNodo<T> * pnodo = nos_a_processar.front();
			nos_a_processar.pop();

			if (pnodo->getEsq() != NULL) {
				nos_a_processar.push(pnodo->getEsq());
				nos_proximo_nivel++;
			}

			if (pnodo->getDir() != NULL) {
				nos_a_processar.push(pnodo->getDir());
				nos_proximo_nivel++;
			}
		}
	}
}

// Como uma Ã¡rvore detÃ©m uma sÃ©rie de nÃ³s que sÃ£o objectos dinÃ¢micos
// localizados na heap, Ã© necessÃ¡rio libertar toda a memÃ³ria associada
// aos nÃ³s antes de se proceder Ã  cÃ³pia.
// Como Ã© possÃ­vel fazer arvoreA = arvoreA, para se evitar apagar
// o objecto Ã  direita do = (que Ã© tambÃ©m o objecto Ã  esquerda)
// Ã© necessÃ¡rio verificar se nÃ£o estamos a fazer atribuiÃ§Ã£o do
// mesmo objecto.

template<class T>
ArvBin<T> & ArvBin<T>::operator=(const ArvBin<T> & o) {
	if (this != &o) {
		// Primeiro liberta toda a memÃ³ria utilizada pela Ã¡rvore actual.
		destroiArv(raiz);

		// Em seguida faz a cÃ³pia da Ã¡rvore Ã  direita do operador =.
		raiz = copiar(o.raiz);
	}

	return *this;
}

// Para resolver esta questÃ£o, usa-se a propriedade das Ã�rvores BinÃ¡rias
// de Pesquisa em que numa visita em ordem, os elementos sÃ£o visitados
// em ordem crescente.

template<class T>
bool ArvBin<T>::E_BST_Valida() {
	if (raiz == NULL)
		return true;

	std::queue<T> valores;
	Valores_Em_Ordem(raiz, valores);

	T valor_anterior;

	valor_anterior = valores.front();
	valores.pop();

	while (!valores.empty()) {
		if (valor_anterior >= valores.front()) {
			return false;
		}

		valor_anterior = valores.front();
		valores.pop();
	}

	return true;
}

template<class T>
void ArvBin<T>::Valores_Em_Ordem(ArvBinNodo<T>* rz, std::queue<T> & valores) const {
	if (rz != NULL) {
		Valores_Em_Ordem(rz->getEsq(), valores);
		valores.push(rz->getInf());
		Valores_Em_Ordem(rz->getDir(), valores);
	}
	return;
}

#endif
